package prictise.com.application1.suanFa;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author zhiyukai
 * @Date 2021.05.06 15:16
 * @Comment 螺旋矩阵2
 */
public class Helix2Matrix {

  private static List<Integer> traverse(int[][] matrix) {
    List ans = new ArrayList();
    if (matrix.length == 0) {
      return ans;
    }
    int R = matrix.length, C = matrix[0].length;
    boolean[][] seen = new boolean[R][C];
    int[] dr = {0, 1, 0, -1};
    int[] dc = {1, 0, -1, 0};
    int r = 0, c = 0, di = 0;
    for (int i = 0; i < R * C; i++) {
      ans.add(matrix[r][c]);
      seen[r][c] = true;
      int cr = r + dr[di];
      int cc = c + dc[di];
      if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]) {
        r = cr;
        c = cc;
      } else {
        di = (di + 1) % 4;
        r += dr[di];
        c += dc[di];
      }
    }
    return ans;
  }


  public static List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> order = new ArrayList<Integer>();
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
      return order;
    }
    int rows = matrix.length, columns = matrix[0].length;
    int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
    while (left <= right && top <= bottom) {
      for (int column = left; column <= right; column++) {
        order.add(matrix[top][column]);
      }
      for (int row = top + 1; row <= bottom; row++) {
        order.add(matrix[row][right]);
      }
//      if (left < right && top < bottom) {
        for (int column = right - 1; column > left; column--) {
          order.add(matrix[bottom][column]);
        }
        for (int row = bottom; row > top; row--) {
          order.add(matrix[row][left]);
        }
//      }
      left++;
      right--;
      top++;
      bottom--;
    }
    return order;
  }

  public int[][] generateMatrix(int n) {
    int[][] result = new int[n][n];
    int c1 = 0;
    int c2 = n - 1;

    int r1 = 0;
    int r2 = n - 1;

    while (r1 < r2 && c1 < c2) {

    }

    return result;
  }

  public static void main(String[] args) {
    int[][] traArray = {
            {1, 2, 3, 4, 5},
            {6, 7, 8, 9, 10},
            {11, 12, 13, 14, 15},
            {16, 17, 18, 19, 20}
//            ,
//            {21, 22, 23, 24, 25}
    };

    List<Integer> res = spiralOrder(traArray);
    int size = res.size();
    for (int i = 0; i < size; i++) {
      System.out.print(res.get(i) + " ");
    }
  }
}
